#include "dijkstra.h"
#include <glib.h>
#include <time.h>



Dijkstra::~Dijkstra()
{
}

const char* Dijkstra::get_nome()
{
  return "Dijkstra";
}

void Dijkstra::makeset(Grafo* &grafo)
{
    GSList* temp = grafo->get_nodi();
    
    while(temp != NULL)
    {
        Nodo* nodo_corrente = ((Nodo *) temp->data);
        set = g_slist_prepend(set, nodo_corrente);
        
        temp = g_slist_next(temp);
    }
}

gint Dijkstra::comparazione_nodi(gconstpointer nodo_a, gconstpointer nodo_b)
{
    gint distanza_a = ((Nodo *)nodo_a)->get_distanza();
    gint distanza_b = ((Nodo *)nodo_b)->get_distanza();
    
    if(distanza_a > distanza_b)
        return 1;
    else if(distanza_a < distanza_b)
        return -1;
    else
        return 0;
}

Nodo* Dijkstra::deletemin()
{
    if(g_slist_length(set) == 0)
        return NULL;

    set = g_slist_sort(set, Dijkstra::comparazione_nodi);

    Nodo* min = (Nodo *) set->data;
    
    set = g_slist_remove(set, min);

	return min;
}

void Dijkstra::esegui(report_function report_func)
{
// Inizializza le distanze
  ostringstream oss;
  clock_t start = clock();
  
  report(report_func, "Inizializzo le distanza a infinito\n");
  grafo_corrente->prepara();

  makeset(grafo_corrente);

  while(true)
  {
    Nodo* nodo = deletemin();

    if(nodo == NULL)
    {
        // Ho finito i nodi da controllare
        clock_t end = clock();
        gfloat secondi = (((gfloat)(end - start))/CLOCKS_PER_SEC);

        oss.str("");
        oss.clear();
        
        oss<<"Esecuzione terminata in ";
        oss.precision(5);
        oss<<secondi<<" secondi"<<endl;    
        report(report_func, oss.str().c_str());
        break; 
    }
    
    oss.str("");
    oss.clear();
    oss<<"Esamino il nodo: "<<nodo->get_indice()<<endl;
    report(report_func, oss.str().c_str());
    
    GSList* temp = grafo_corrente->get_archi();
    while(temp != NULL)
    {
      Arco* arco_corrente = ((Arco *) temp->data);

      if(arco_corrente->get_origine()->get_indice() == nodo->get_indice())
      {
        // Escludo i possibili nodi non raggiungibili, il nodo di partenza non può avere distanza infinita        
        // Relax
        if(nodo->get_distanza() < G_MAXINT &&
           nodo->get_distanza() + arco_corrente->get_lunghezza() < arco_corrente->get_destinazione()->get_distanza())
          {
            gint distanza_originale = arco_corrente->get_destinazione()->get_distanza();
            
            oss.str("");
            oss.clear();
            oss<<"\tRelax("<<nodo->get_indice()<<", "<<arco_corrente->get_destinazione()->get_indice()<<") da ";
            if(distanza_originale == G_MAXINT)
                oss<<"infinito";
            else
                oss<<distanza_originale;
            oss<<" a "<<(nodo->get_distanza()+arco_corrente->get_lunghezza())<<endl;
            report(report_func, oss.str().c_str());
            
            arco_corrente->get_destinazione()->set_distanza(nodo->get_distanza() + arco_corrente->get_lunghezza());
            arco_corrente->get_destinazione()->set_precedente(nodo);
          } else
          { 
            oss.str("");
            oss.clear();
            oss<<"\tRelax("<<nodo->get_indice()<<", "<<arco_corrente->get_destinazione()->get_indice()<<") non ha bisogno di rilassamento"<<endl;
            report(report_func, oss.str().c_str());
          }
      }
      
      temp = g_slist_next(temp);
    }
  }
}
